package gen.tree;

public class Tree<K extends Comparable<K>,V> {
	private TreeNode<K,V> root;
	
	public Tree() {
		root = null;
	}
	
	public Tree(K key, V value)	{
		root = new TreeNode<K, V>(key,value);
	}
	
	public void setRoot(TreeNode<K,V> root)	{
		this.root = root;
	}
	
	public TreeNode<K,V> getRoot() {
		return root;
	}
	
	/**
	 * Get a string representing the tree in pre-order form
	 * 
	 * @return the string in pre-order form 
	 */
	public String preorder() {
		return preorder(root);
	}
	
	private String preorder(TreeNode<K,V> t) {
		if (t == null)
			return "";
		else
			return t.toString() + preorder(t.getLeft()) + preorder(t.getRight());
	}
	
	/**
	 * Get a string representing the tree in post-order form
	 * 
	 * @return the string in post-order form 
	 */
	public String postorder() {
		return postorder(root);
	}
	
	private String postorder(TreeNode<K,V> t) {
		if (t == null)
			return "";
		else
			return postorder(t.getLeft()) + postorder(t.getRight()) + t.toString();
	}
	
	/**
	 * Get a string representing the tree in in-order form
	 * 
	 * @return the string in in-order form 
	 */
	public String inorder() {
		return inorder(root);
	}
	
	private String inorder(TreeNode<K,V> t)	{
		if (t == null)
			return "";
		else
			return inorder(t.getLeft()) + t.toString() + inorder(t.getRight());
	}
	
	/**
	 * Get a string representing the tree in level-order form
	 * 
	 * @return the string in level-order form 
	 */
	public String levelorder() {
		String str = "";
		java.util.LinkedList<TreeNode<K,V>> list = new java.util.LinkedList<TreeNode<K,V>>();
		list.add(root);
		while (list.size() != 0) {
			TreeNode<K,V> node = list.remove();
			if (node != null){
				str += node.toString();
				if (node.getLeft() != null)
					list.add(node.getLeft());
				if (node.getRight() != null)
					list.add(node.getRight());
			}
		}
		return str;
	}
	
	/**
	 * Insert a node into the tree
	 * 
	 * @param key the key of the node to insert
	 * @param value the value of the node to insert
	 */
	public void insert(K key, V value) {
		if (key != null)
				root = insert(root, key, value);
	}
	
	private TreeNode<K,V> insert(TreeNode<K,V> t, K key, V value) {
		if (t == null)
			t = new TreeNode<K,V>(key, value);
		else if (key.compareTo(t.getKey()) < 0)
			t.setLeft(insert(t.getLeft(), key, value));
		else if (key.compareTo(t.getKey()) > 0)
			t.setRight(insert(t.getRight(), key, value));
		return t;
	}
	
	/**
	 * Remove a node in the tree
	 * 
	 * @param key The key of the node to remove
	 */
	public void remove(K key) {
		root = remove(root, key);
	}
	
	private TreeNode<K,V> remove(TreeNode<K,V> t, K key) {
		if (t == null)
			t = null;
		else if (key.compareTo(t.getKey()) < 0)
			t.setLeft(remove(t.getLeft(), key));
		else if (key.compareTo(t.getKey()) > 0)
			t.setRight(remove(t.getRight(), key));
		else if (key.compareTo(t.getKey()) == 0) {
			if (t.getRight() == null)
				t = t.getLeft();
			else if (t.getLeft() == null)
				t = t.getRight();
			else {
				TreeNode<K, V> temp = getSucc(t);
				if (temp == null)
					t = null;
				else {
					t.setKey(temp.getKey());
					t.setValue(temp.getValue());
					t.setRight(remove(t.getRight(), temp.getKey()));
				}
			}
		}
		return t;
	}
	
	/**
	 * Get the successor of a node in the tree
	 * 
	 * @param t The node whose successor is needed
	 * @return the successor of the node
	 */
	public TreeNode<K,V> getSucc(TreeNode<K,V> t) {
		if (t == null)
			return null;
		else if (t.getLeft() == null)
			return t.getRight();
		else if (t.getRight() == null)
			return t.getLeft();
		else
			return getSuccHelper(t.getRight());
	}
	
	private TreeNode<K, V> getSuccHelper(TreeNode<K, V> t) {
		if (t.getLeft() == null)
			return t;
		else 
			return getSuccHelper(t.getLeft());
	}
	
	/**
	 * Get the value of a node in the tree
	 * 
	 * @param key The key of the node whose value is needed
	 * @return The value of the node
	 */
	public V find(K key) {
		return find(root, key);
	}
	
	private V find(TreeNode<K,V> t, K key) {
		if (t == null)
			return null;
		else if (key.compareTo(t.getKey()) < 0)
			return find(t.getLeft(), key);
		else if (key.compareTo(t.getKey()) > 0)
			return find(t.getRight(), key);
		else
			return t.getValue();
	}
}